1. References
The following papers provide useful background information, for which they are incorporated herein by reference in their entirety, and are selectively referred to in the remainder of this disclosure by their accompanying reference symbols in square brackets (i.e., [JaS'03] for the paper by A. Jas et al):
[ITRS'01] International technology roadmap for semiconductors, 2001 edition (http://public.itrs.net)
[TestKompress] TestKompress, Mentor Graphics, http://www.mentor.com
[SoCBIST] SoCBIST, Synopsys, http://www.synopsys.com
[VirtualScan] VirtualScan, SynTest, http://www.syntest.com
[Jas'03] A. Jas, J. Ghosh-Dastidar, Mom-Eng Ng, N. A. Touba, “An efficient test vector compression scheme using selective Huffman coding”, in IEEE Trans. Computer-Aided Design, Vol. 22, No. 6, June 2003
[Jas'98] A. Jas, N. A. Touba, “Test vector decompression via cyclical scan chains and its application to testing core-based designs”, in Proc. International Test Conference, pp. 458-464, 1998
[Chandra'03] A. Chandra, K. Chakrabarty, “Test data compression and test resource partitioning for system-on-a-chip using frequency-directed run-length codes”, in IEEE Trans. on Computers, Vol. 52, No. 8, August 2003
[Chandra'01] A. Chandra, K. Chakrabarty, “System-on-a-chip test compression and decompression architectures based on golomb codes”, in IEEE Trans. Computer-Aided Design, Vol. 20, pp. 355-368, March 2001
[Chandra'02] A. Chandra, K. Chakrabarty, “Test data compression and decompression based on internal scan chains and Golomb coding”, in IEEE Trans. Computer-Aided Design, Vol. 21, pp. 715-722, June 2002
[Golomb'66] S. W. Golomb, “Run-length encoding,” in IEEE Trans. Inform. Theory, vol. IT-12, pp. 399-401, December 1966
[Huff'52] D. A. Huffman, “A Method for the construction of mini-mum redundancy codes”, in Proc. IRE, vol. 40, 1952, pp. 1098-1101.
[Wolff'02] F. G. Wolff, C. Papachristou, “Multiscan-based test compression and hardware decompression using LZ77”, in Proc. International Test Conference, pp. 331-339, 2002
[Li'03] L. Li, K. Chakrabarty, “Test data compression using dictionaries with fixed length indices”, in Proc. VLSI Test Symposium, pp. 219-224, 2003
[Koenemann'91] B. Koenemann, “LFSR-coded test patterns for scan designs”, in Proc. European Test Conference, pp. 237-242, 1991
[Rajski'02] J. Rajski, M. Kassab, N. Mukherjee, R. Thompson, K. Tsai, A. Hertwig, N. Tamarapalli, G. Mrugalski, G. Eide, J. Qian, “Embedded deterministic test for low cost manufacturing test”, in Proc. International Test Conference, pp. 301-310, 2002
[Rajski'03] G. Mrugalski, J. Rajski, J. Tyszer, “High speed ring generators and compactors of test data”, in Proc. IEEE VLSI Test Symposium, pp. 57-62, 2003
[Rajski'00] J. Rajski, N. Tamarapalli, J. Tyszer, “Automated synthesis of phase shifters for built-in self-test applications”, in IEEE Trans. on Computer-Aided Design, Vol. 19, pp. 1175-1188, October 2000
[Krishna'98] C. Krishna, A. Jas, N. A. Touba, “Test vector encoding using partial LFSR reseeding”, in Proc. International Test Conference, pp. 885-893, 2001
[Rajski'98] J. Rajski, J. Tyszer, N. Zacharia, “Test data decompression for multiple scan designs with boundary scan”, in IEEE Trans. on Computers, Vol. 47, pp. 1188-1200, 1998
[Wohl'03] P. Wohl, J. A. Waicukauski, S. Patel, M. B. Amin, “Efficient compression and application of deterministic patterns in a Logic BIST architecture”, in Proc. Design Automation Conference, pp. 566-569, 2003
[Balakrishnan'03] K. J. Balakrishnan, N. A. Touba, “Deterministic test vector decompression in software using linear operations”, in Proc. VLSI Test Symposium, pp. 225-231, 2003
[Chak'93] S. T. Chakradhar, V. D. Agrawal and S. G. Roth-Weiler, “A transitive closure algorithm for test generation”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 12, No. 7, pp. 1015-1028, July 1993.
[Hwang'02] S. Hwang, J. A. Abraham, “Optimal BIST using an embedded microprocessor”, in Proc. International Test Conference, pp. 736-745, 2002
[Miron] M. Abramovici, M. A. Breuer, A. D. Friedman, Digital systems testing and testable design, Computer science press, New York, N.Y. 10010
[Xtensa] Xtensa microprocessor, Tensilica Inc. (http://www.tensilica.com)
[ARC] ARCtangent processor, Arc International (http://www.arc.com)
2. Overview
Test cost per chip is increasing and threatens the ability to cost-effectively design and manufacture larger and larger ICs [ITRS'01]. A major percentage of the test cost comes from the capital required for the automatic test equipment (ATE). Different approaches for reducing ATE cost have been explored, which include                Lowering the time spent by the ATE per chip by reducing the test application time.        Avoiding reloading of the ATE memory by decreasing the test set size        Exploiting support from on-chip test HW and using inexpensive ATE        Storing compressed data in the ATE memory that can be de-compressed on-chip before application.        
The last approach, also referred to as test data compression, has matured in recent years, and is a useful technique for reducing rising test costs, and the explosion in the volume of data that has to be transported between the ATE and the chip under test. In test data compression, test patterns are compressed offline (during test generation) and the compressed data is stored on the tester. The tester applies this data to the chip under test and on-chip decompression hardware helps to recover the original test patterns from the compressed data.
For test responses, on-chip circuitry compresses the patterns, and the compressed response data is sent to the tester, which compares the compressed responses with the golden (correct) responses. Existing work in the field of test data compression [Jas'03, Jas'98, Chandra'01, Chandra'03, Wolff'02, Li'03, Rajski'02] explores the use of different compression/decompression algorithms and techniques to reduce test set size and test application time for a given circuit. Commercial tools that are capable of providing a test compression solution for a wide range of circuits include: Embedded Deterministic Test or Test-Kompress™ [TestKompress], SoCBIST™ [SoCBIST], and VirtualScan™ [VirtualScan].
Several approaches for compressing test data [Jas'98, Jas'03, Chandra'01, Chandra'02, Chandra'03, Wolff'02, Li'03] are based on existing compression schemes (statistical encoding, dictionary based methods, etc). Test data compression based on statistical encoding techniques like Huffman, Golomb and run-length encoding are presented in [Jas'03, Chandra'03, Chandra'02, Chandra'01, Jas'98]. While huffman coding encodes fixed length words in test data into variable length code words, run-length coding encodes variable length words into fixed length code words. Golomb coding encodes a variable length word to a variable length code word. The extent of compression that can be achieved using the above-mentioned statistical techniques also depends on the distribution of fixed/variable length words in the test data. Input data statistics play an important role in deciding the compression ratio.
Compression ratio can be improved by increasing the frequency of occurrence of selected words is by using a cyclical scan register [Jas'98]. But a major drawback with the above approach is the need for the cyclical scan register to be as long as the scan chain itself. Hence, there is a 100% hardware overhead in terms of the number of memory elements. The use of boundary scan or scan chains in other cores, not under test, as cyclical scan register reduces the hardware overhead [Jas'98]. But, this may involve significant routing overhead. Moreover, existence of boundary scan or scan chains in other cores matching the length of each scan chain in a given core is not guaranteed.
Techniques have been proposed in [Chandra'01, Chandra'02, Chandra'03] where the test difference vector is evaluated with respect to the circuit response and is compressed using golomb codes. Although, this results in a lower hardware overhead, they require an additional feedback to the ATE during decompression.
Dictionary-based test compression schemes were presented in [Wolff'02, Li'03]. These methods select strings of symbols to create a dictionary, and then encode them into equal-size code words using the dictionary. The dictionary stores the strings, and it may be either static or dynamic. The compression algorithm LZ77 is based on a dynamic dictionary and uses part of the previously seen input stream (window) as dictionary [Wolff'02]. In general, increasing the window size increases the compression ratio, which in turn implies the need for increased memory re-sources. An important step in constructing the static dictionary is to select the entries in the dictionary. This involves identifying “compatible” words that can be represented with the same dictionary entry. This is similar to the clique-partitioning problem [Li'03]. The words are mapped to the nodes of the graph and two nodes are connected if the corresponding words are “compatible”.
Other methods [Rajski'98, Krishna'98, Wohl'02] for com-pressing test data use a linear feedback shift register (LFSR) to encode multiple test patterns into a single LFSR seed. In order to avoid any reduction in fault coverage, very large sized LFSR's (256-400 bits) [Wohl'02] are used to encode the test vectors of moderately sized circuits. Another approach called embedded deterministic test (EDT) [Rajski'02] obtains spatial compression by using a modified LFSR followed by a phase shifter. The phase shifter enables the use of a reasonable sized LFSR (24-32 bits) to feed a large number of scan chains. All the above techniques exploit the fact that the test cubes frequently feature a large number of unspecified positions. Hence, the compression scheme interacts with the ATPG algorithm to maximize compression. Recent work [Hwang'02] explores the use of an embedded microprocessor for executing the linear operations of a LFSR. The decompression speed is further improved by using “word-based” linear operations in the software implementations of the LFSR, which expands the compressed test data into the corresponding deterministic test vectors [Balakrishnan'03].
Related technologies for test data compression do not best exploit the hierarchical structure of modern integrated circuits, or Systems-on-chip (System LSI). For example, related technologies do not re-use the hardware for test decompression across different on-chip components or cores. Further, they do not allow for a composition of multiple, different compression algorithms for a single circuit. Finally, current test compression technologies do not provide a solution that is truly scalable across the needs of a wide range of circuits.